Міністерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра комп’ютерних наук
ЛАБОРАТОРНА РОБОТА №6
з дисципліни “Теорія алгоритмів”
Тема роботи: Оцінка складності алгоритмів
Лабораторна робота №6
Тема роботи: Оцінка складності алгоритмів
Мета роботи: Вивчення теоретичних та практичних методів оцінки складності алгоритмів.
Теоретичні відомості
Оцінка складності алгоритмів
Важливим етапом розробки алгоритмів є аналіз алгоритмів та оцінка їх складності. Cкладністю алгоритму ( називають деяке число (, яке є результатом обчислення функціоналу М(()=(, заданого на множині алгоритмів А((. Причинами, які приводять до необхідності аналізу складності алгоритмів є:
потреба в попередній оцінці ресурсів ЕОМ (об’єму оперативної та постійної пам’яті, швидкодії процесора), достатніх для реалізації для реалізації алгоритмів;
встановлення кількісних критеріїв для порівнянні різних алгоритмів вирішення одної задачі;
встановлення критерію оптимальності алгоритму (оптимальність в даному випадку слід розуміти як неможливість покращення заданих характеристик алгоритму.)
прогнозування змін вимог до обчислювальних ресурсів та критеріїв оцінки алгоритмів при зміні характеру та кількості вхідних даних.
Складність алгоритму, як правило, включає необхідний об’єм оперативної та постійної пам’яті, та час виконання алгоритму, взяті з певними ваговими коефіцієнтами. В окремих випадках доступні ресурси ЕОМ можуть бути більші за необхідні для виконання алгоритму (наприклад об’єм оперативної пам’яті ЕОМ більший за об’єм пам’яті, необхідний алгоритму). В таких випадках при розрахунку складності алгоритму можна не враховувати відповідні складові.
Об’єм оперативної та постійної пам’яті, необхідної для розміщення даних алгоритму можна визначити виходячи з переліку змінних програми, їх типів, характеру розміщення змінних у пам’яті (так, наприклад, розміщення змінних у пам’яті та час їх існування для алгоритмів , реалізованих мовами програмування С++ або Паскаль визначається моделлю пам’яті програми, класом пам’яті конкретних змінних, та порядком використання функцій виділення та вивільнення динамічної пам’яті та роботи з файлами), тобто залежить як від самого алгоритму так і від засобів його реалізації.
Час виконання алгоритму залежить від структури алгоритму (тобто послідовності і виду команд), часу виконання кожної команди, об’єму і характеру вхідних даних. Оскільки час виконання команди є характеристикою ЕОМ а не алгоритму, то при оцінці складності алгоритму доцільно замість часу виконання взяти кількість команд, виконану алгоритмом, або, якщо час виконання команд різний, кількість тактів процесора.
При оцінці впливу вхідних даних на складність алгоритму використовують такий показник як розмірність задачі n. В багатьох задачах n є просто скаляр, рівний, наприклад, числу вершин графа задачі. В загальному випадку n може бути вектором або матрицею, елементи якої є розмірами масивів вхідних даних. Вплив характеру вхідних даних на складність алгоритму (особливо актуально для алгоритмів з розгалуженнями) враховують, проводячи оцінку максимальної, мінімальної та середньої кількості операцій.
Функцію , яка дає верхню границі кількості операцій, що виконує алгоритм при вирішенні будь-якої задачі розмірності n, називають робочою функцією.
Кажуть що функція порядку (позначають ), якщо .
Функція вищого порядку малості ніж (позначають ), якщо .
Алгоритм називають поліноміальним якщо його робоча функція , де - поліном від n степені m: . В іншому випадку алгоритм називають експоненціальним.
Аналогічні оцінки можна провести і для середньої та мінімальної кількості опер0,ацій. На практиці поліноміальні алгоритми добре піддаються виконанню на ЕОМ при зростанні n, а експоненціальні швидко перевантажують ЕОМ. Так алгоритм вирішення задачі комівояжера, який має робочу функцію , при n=20 вимагає для вирішення близько 70 століть машинного часу.
Для оцінки середньої кількості операцій можна використа...
